/*
 * @lc app=leetcode.cn id=680 lang=swift
 *
 * [680] 验证回文字符串 Ⅱ
 */

// @lc code=start
class Solution {
    func validPalindrome(_ s: String) -> Bool {
        return isPalindrome(Array(s), deletableLetterCount: 1)
    }
    
    func isPalindrome(_ characters: [Character], deletableLetterCount: Int) -> Bool {
        var left = 0, right = characters.count - 1
        while left < right {
            if characters[left].isLetter == false && characters[left].isNumber == false {
                left += 1
                continue
            }
            if characters[right].isLetter == false && characters[right].isNumber == false {
                right -= 1
                continue
            }
            
            if characters[left].lowercased() == characters[right].lowercased() {
                left += 1
                right -= 1
            }else{
                if deletableLetterCount <= 0{
                    return false
                }else{
                    //删除左边或者右边的一个字符，看是否是回文字符串
                    return isPalindrome(Array(characters[left ..< right]), deletableLetterCount: 0) ||
                        isPalindrome(Array(characters[left+1 ... right]), deletableLetterCount: 0)
                    
                }
                
            }
        }
        return true
    }
}
// @lc code=end

